package l.l.w.leetcode.MedianofTwoSortedArrays;

/**
 * Created by llw on 2017/8/25.
 */
public class MedianofTwoSortedArrays {

    /**
     * 时间复杂度1/2 O(n+m),
     * 最基础的做法，遍历，组合成一个新的数组，然后计数，直到找到中位数的位置
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {

        //assert not null
        if(nums1==null){
            if(nums2.length %2 ==1)
                return nums2[(nums2.length-1)/2];
            else
                return (nums2[(nums2.length-1)/2]+nums2[nums2.length/2])/2.0;
        }
        if(nums2==null){
            if( nums1.length %2 ==1)
                return nums1[( nums1.length-1)/2];
            else
                return (nums1[( nums1.length-1)/2]+nums1[ nums1.length/2])/2.0;
        }
        int m = nums1.length;
        int n=nums2.length;
        int allLength = n+m;

        int mid = (n+m-1)/2;
        int i = 0,j=0,k = 0;
        int[] all = new int[mid+1];
        for(; i < m && j<n;){
            if(nums1[i] <= nums2[j]){
                all[k]=nums1[i];
                i++;
            }
            else {
                all[k]=nums2[j++];
            }
            if(k==mid){
                if(allLength %2 ==1){
                    return all[k];
                }else{
                    if(i==m){
                        return (all[k]+nums2[j])/2.0;
                    }else if(j == n){
                        return (all[k]+nums1[i])/2.0;
                    }else{
                        return (all[k]+Math.min(nums1[i],nums2[j]))/2.0;
                    }
                }
            }
            k++;
        }
        if(i >=m ){
            if(allLength %2 ==1)
                return nums2[mid-m];
            else
                return (nums2[mid-m]+nums2[mid-m+1])/2.0;
        }else{
            if(allLength %2 ==1)
                return nums1[mid-n];
            else
                return (nums1[mid-n]+nums1[mid-n+1])/2.0;
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1==null){
            if(nums2.length %2 ==1)
                return nums2[(nums2.length-1)/2];
            else
                return (nums2[(nums2.length-1)/2]+nums2[nums2.length/2])/2.0;
        }
        if(nums2==null){
            if( nums1.length %2 ==1)
                return nums1[( nums1.length-1)/2];
            else
                return (nums1[( nums1.length-1)/2]+nums1[ nums1.length/2])/2.0;
        }
        //在短的数组中进行二分查找
        if(nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        int allLength = m+n;
        int imin = 0;
        int imax = m;
        int i=0,j=0;
        while(imin <= imax){
            i = (imin + imax)/2;
            j = (m+n+1)/2-i;
            if(i < m && nums2[j-1] > nums1[i]){
                imin = i+1;
            }else if(i > 0 && nums1[i-1] > nums2[j]){
                imax = i-1;
            }else break;
        }
        int leftA=0,leftB=0;
        if(i==0) {
            leftA = Integer.MIN_VALUE;
            leftB = nums2[j-1];
        }
        else if(j ==0){
            leftA = nums1[i-1];
            leftB = Integer.MIN_VALUE;
        }else{
            leftA = nums1[i-1];
            leftB = nums2[j-1];
        }
        if(allLength%2 ==1){
            return Math.max(leftA,leftB);
        }else{
            int rightA=0, rightB=0;
            if(i == m){
                rightA = Integer.MAX_VALUE;
                rightB = nums2[j];
            }else if(j == n){
                rightA = nums1[i];
                rightB = Integer.MAX_VALUE;
            }else{
                rightA = nums1[i];
                rightB = nums2[j];
            }
            return  (Math.max(leftA,leftB)+Math.min(rightA,rightB))/2.0;
        }
    }
    public static void main(String[] args) {
        int[] nums2 = {1,2};
        int[] nums1 = {3,4};
        double median = new MedianofTwoSortedArrays().findMedianSortedArrays(nums1, nums2);
        System.out.println(median);
    }
}
